package formal.tree.bst;

import java.util.ArrayList;
import java.util.List;

/**
 * todo E_108的进阶版?
 * 将有序链表转换为二叉搜索树
 *
 * @author DengYuan2
 * @create 2021-01-24 21:50
 */
public class M_109 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(-10);
        ListNode n2 = new ListNode(-3);
        ListNode n3 = new ListNode(0);
        ListNode n4 = new ListNode(5);
        ListNode n5 = new ListNode(9);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        TreeNode node = sortedListToBST(n1);
        System.out.println(node);
    }

    /**
     * 我的思路-转换成E_108
     *
     * @param head
     * @return
     */
    public static TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>(16);
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        return toBST(list, 0, list.size() - 1);
    }

    public static TreeNode toBST(List<Integer> list, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = toBST(list, left, mid - 1);
        node.right = toBST(list, mid + 1, right);
        return node;
    }

    /**
     * 大神的写法-和官方的分治很类似
     *
     * @param head
     * @return
     */
    public static TreeNode sortedListToBST2(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode pre = findPre(head);
        ListNode mid = pre.next;
        //注意：断开链表
        pre.next = null;
        TreeNode root = new TreeNode(mid.val);
        root.left = sortedListToBST2(head);
        root.right = sortedListToBST2(mid.next);
        return root;
    }

    public static ListNode findPre(ListNode head) {
        //因为至少有2个节点，所以下面这个可以省略
//        if (head == null) {
//            return null;
//        }
        //中间节点的前一个节点
        ListNode pre = head;
        //slow为中间节点
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        return pre;
    }

    /**
     * 官方- 分治+中序遍历 -上面方法的时间复杂度的瓶颈在于寻找中位数节点。由于构造出的二叉搜索树的
     * 中序遍历结果就是链表本身，因此我们可以将分治和中序遍历结合起来，减少时间复杂度
     * ！半懂半不懂！
     */
    public static ListNode node=null;
    public static TreeNode sortedListToBST3(ListNode head) {
        if (head == null) {
            return null;
        }
        node=head;
        int length = 0;
        ListNode tmp = head;
        while (tmp != null) {
            length++;
            tmp = tmp.next;
        }
        return helper(0, length - 1);
    }

    public static TreeNode helper(int left, int right) {
        if (left>right){
            return null;
        }
//        int mid = (left+right)/2;也可以哦
        int mid = (left + right+1) / 2;
        //关键：二叉树中序遍历的结果和链表的结果一致啊！！！
        TreeNode root = new TreeNode();
        root.left=helper(left,mid-1);
        root.val=node.val;
        node=node.next;
        root.right=helper(mid+1,right);
        return root;

    }

}
